//== SAGITTARIUS ============================================================================

//== FILEDOC =========================================================================

/** @file reCS.h
  * @brief Character sets for regular expressions
  * @details Supports intersection, union, etc. on character sets.
  * These sets are fundamentally based on the concept of ranges, to
  * reduce memory usage & improve performance where the same property
  * or action is associated with all of the members of a range (as is
  * common in lexers). Charsets can use either a fixed or arbitrary
  * precision type for the basic symbol type.
  */

//== BEGINNING OF CODE ===============================================================

#ifndef __SAGUTTARUIS__RECS__H_
#define __SAGUTTARUIS__RECS__H_

//== INCLUDES ========================================================================

#include "sagittarius/core/SagittariusCore.h"
#include "sagittarius/lexer/lexcore.h"

///Least character in alphabet
#define CONST_RE_ALPHAMIN  0x00000

///Start of backref chars
#define CONST_RE_BACKREF0  0xF1000

///Represents positive infinity for ranges
#define CONST_RE_ALPHAMAX  0xF0000
///Special re representing the empty string
#define CONST_RE_EMPTY_STR 0xF0001 
///Special re representing the empty language
#define CONST_RE_NULL      0xF0002
///???
#define CONST_RE_MAX       0xF0103

#ifdef __cplusplus
extern "C" {
#endif

//-- RE Character Sets --

/**
 * @brief A struct representing a range of values
 * @details Represents the range [l,u] inclusive (i.e. l and u
 * are part of the range.
 */
typedef struct {
    /// @brief The lower bound
    LXAlphaType l;
    
    /// @brief The upper bound
    LXAlphaType u;
} RECS_Range;

/**
 * @brief A pair of ranges
 */
typedef struct {
    RECS_Range* p;
    RECS_Range* q;
} RE_RangePair;

/**
 * @fn int re_rangeIsValid(const RECS_Range* r) */
int re_rangeIsValid(RECS_Range r);

/**
 * @fn RECS_Range re_constructRange(const LXAlphaType l, const LXAlphaType u) */
RECS_Range re_constructRange(LXAlphaType l, LXAlphaType u);

/**
 * @fn RECS_Range re_constructRangeFixed(LXFixedType l, LXFixedType u) */
RECS_Range re_constructRangeFixed(LXFixedType l, LXFixedType u);

/**
 * @fn RECS_Range re_constructRangeS(const LXAlphaType x)
 * @brief Works for a single symbol */
RECS_Range re_constructRangeS(LXAlphaType x);

/**
 * @fn void re_copyRange(RECS_Range* res, RECS_Range r) */
//void re_copyRange(RECS_Range* res, RECS_Range r);

/**
 * @fn void re_deleteRange(RECS_Range* r) */
void re_deleteRange(RECS_Range* r);

/**
 * @fn int re_compareRange(const RECS_Range r) */
int re_compareRanges(RECS_Range r, RECS_Range s);

/**
 * @brief Gives the # of elts in the range
 * @param[in] r A range
 * @param[out] res Set to r.u - r.l + 1
 */
void re_rangeDiam(LXAlphaType* res, RECS_Range r);

/**
 * @fn int re_printRange(const RECS_Range r) */
//int re_printRange(RECS_Range r);

/**
 * @brief Write the character @a x
 */
void re_writeAlpha(int fd, LXAlphaType x);

/**
 * @fn int re_writeRange(int fd, RECS_Range r) */
int re_writeRange(int fd, RECS_Range r);

/**
 * @fn const RECS_Range* re_rangeMin(const RECS_Range* p, const RECS_Range* q) */
//const RECS_Range* re_rangeMin(const RECS_Range* p, const RECS_Range* q);

/**
 * @fn RE_RangePair re_sortRanges(const RECS_Range* p, const RECS_Range* q) 
 * @brief Sort p,q -> r,s, where lb(r) <= lb(s)*/
//RE_RangePair re_sortRanges(const RECS_Range* p, const RECS_Range* q);

/**
 * @brief Looks like it would sort pt & qt but is not used in the source
 */
#define RE_SORT_RANGES(pt, qt, p, q) RE_RangePair resr_tmp = re_sortRanges(pt, qt); p = resr_tmp.p; q = resr_tmp.q

/**
 * @brief Determine if two ranges intersect
 * @param[in] p Operand
 * @param[in] q Operand
 * @return 1 if p and q intersect in a non-empty set, 0 otherwise
 */
int re_rangesIntersect(RECS_Range p, RECS_Range q);

/**
 * @brief Determine if two ranges contact
 * @details Unlike @ref re_rangesIntersect, will return true if ranges are adjacent (e.g. [a,b], [c,d])
 * The two disjoint ranges can then be united to give an equivalent set.
 * @param[in] p Operand
 * @param[in] q Operand
 * @return 1 if p and q intersect or are adjacent
 */
int re_rangesContact(RECS_Range p, RECS_Range q);

/**
 * @brief Intersect two ranges
 * @param[out] r The result of the intersection (p ∩ q)
 * @param[in] p Operand
 * @param[in] q Operand
 */
void re_intersectRanges(RECS_Range* r, RECS_Range p, RECS_Range q);

/**
 * @brief Unite two ranges
 * @param[out] r The result of the union (p ∪ q)
 * @param[in] p Operand
 * @param[in] q Operand
 */
void re_uniteRanges(RECS_Range* r, RECS_Range p, RECS_Range q);

/**
 * @brief A set of characters
 * @details The implementation is based on zero (for the empty set)
 * or more ranges. A range may be degenerate, i.e. reduce to a single
 * element. A range may not be empty
 */
typedef struct {
    /// Number of ranges
    uint32 n;
    
    /**
     * @brief Range array integrated into struct
     * @details The struct is allocated like this:
     * malloc(sizeof(RE_CharSet) + (@a n - 1)*sizeof(RECS_Range)).<br>
     * This creates space for @a n ranges within the block. Previously,
     * C99 flexible array members were used, but C99 support is not 
     * widespread enough to allow this sort of implementation
     */
    RECS_Range ranges[1];
} RE_CharSet;

/**
 * @brief The empty set
 * @return @ref RE_CharSet representing the empty set
 */
RE_CharSet* re_createCSEmpty();

/**
 * @brief The full alphabet as a charset
 * @return @ref RE_CharSet representing the full alphabet
 */
RE_CharSet* re_createCSFull();

/**
 * @brief Creates a set from a single symbol
 */
RE_CharSet* re_createCSSym(LXConstAlphaType x);

/**
 * @brief Creates a set from a single (fixed) symbol
 */
RE_CharSet* re_createCSFixed(LXFixedType x);

/**
 * @brief Creates a set representing the null language
 * @details The null language is treated as a special symbol in this implementation
 */
RE_CharSet* re_createCSNull();

/**
 * @brief Creates a set representing the empty string
 * @details The empty string is treated as a special symbol in this implementation
 */
RE_CharSet* re_createCSEmptyStr();

/**
 * @brief Creates a set comprising the range [l,u] inclusive
 */
RE_CharSet* re_createCSRange(LXConstAlphaType l, LXConstAlphaType u);

/**
 * @brief Copy constructor
 * @returns A copy of @a s
 */
RE_CharSet* re_copyCS(RE_CharSet* s);

/**
 * @brief Creates complement of the given char set
 * @param[in] p Character set. Must be sorted.
 * @details REQUIRES that the set @a p be sorted
 */
RE_CharSet* re_CSComplement(RE_CharSet* p);

/**
 * @fn RE_CharSet* re_destroyCS(RE_CharSet* cs)
 * @brief Frees memory */
void re_destroyCS(RE_CharSet* cs);

/**
 * @fn int re_CSisEmpty(RE_CharSet* cs)
 * @brief Returns true if set is empty */
int re_CSisEmpty(RE_CharSet* cs);

/**
 * @fn int re_CSisSymbol(RE_CharSet* cs)
 * @brief Returns true if set consists of a single symbol */
int re_CSisSymbol(RE_CharSet* cs);

/**
 * @fn int re_CSisNull(RE_CharSet* cs) */
int re_CSisNull(RE_CharSet* cs);

/**
 * @fn int re_CSisEmptyStr(RE_CharSet* cs) */
int re_CSisEmptyStr(RE_CharSet* cs);

/**
 * @brief Does @a cs contain the whole alphabet?
 * @returns 1 if @a cs is the whole alphabet, 0 otherwise
 */
int re_CSisFull(RE_CharSet* cs);

/**
 * @fn LXAlphaType re_CSgetSymbol(RE_CharSet* cs)
 * @brief Returns the alpha val if the character set consists only of a single symbol */
LXAlphaType re_CSgetSymbol(RE_CharSet* cs);

/**
 * @fn RE_CharSet* re_CSSymComp(RE_CharSet* cs, const LXAlphaType x) */
int re_CSSymComp(RE_CharSet* cs, LXAlphaType x);

/// r is less than s
#define RECS_COMPARE_LT 1
/// r is equal to s
#define RECS_COMPARE_EQ 2
/// r is greater than s
#define RECS_COMPARE_GT 3

/**
 * @brief Give the order relation between two charsets
 * @returns @ref RECS_COMPARE_LT if r < s, @ref RECS_COMPARE_EQ if r == s, @ref RECS_COMPARE_GT otherwise
 */
int re_compareCS(RE_CharSet* r, RE_CharSet* s);

/**
 * @brief Equality test: r == s
 * @returns 1 if r == s, 0 otherwise
 */
int re_CSeq(RE_CharSet* r, RE_CharSet* s);

/**
 * @brief Lower bound
 * @returns The lower bound of p
 */
void re_CSlb(LXAlphaType* r, RE_CharSet* p);

/**
 * @brief Upper bound
 * @returns The upper bound of p
 */
void re_CSub(LXAlphaType* r, RE_CharSet* p);

/**
 * @fn int re_printCS(const RE_CharSet* s) */
int re_printCS(RE_CharSet* s);

/**
 * @brief Write the charset to stdout etc.
 * @param fd File descriptor
 * @param s The set
 * @details Dumps a visual representation of the charset to the specified file descriptor
 */
void re_writeCS(int fd, RE_CharSet* s);

/**
 * @brief Does a charset contain a particular element?
 * @param[in] cs The set
 * @param[in] x An element
 * @returns 1 if @a x ∈ @a cs
 */
int re_CSContains(RE_CharSet* cs, LXAlphaType x);

/**
 * @brief Samples the charset
 * @param[in] cs The set to be sampled
 * @returns A character in cs
 * @details Samples an arbitrary character from @a cs.
 */
LXAlphaType re_CSsample(RE_CharSet* cs);

/**
 * @brief Get number of elements of the set
 * @param[in] cs The set
 * @param[out] r Set to the number of elements in cs
 */
void re_CScount(LXAlphaType* count, RE_CharSet* cs);

/**
 * @brief Intersects a range with a set
 * @param[in] r The range
 * @param[in] s The charset
 * @returns A @ref RE_CharSet representing the result of the intersection between @a r and @a s
 */
RE_CharSet* re_intersectRangeSet(RECS_Range r, RE_CharSet* s);

/**
 * @brief Union operation between a range and a set
 * @param[in] r A range
 * @param[in] s A set
 * @returns The union of r with s
 * @details Provides a basic operation required by @ref re_CSUnion
 */
RE_CharSet* re_uniteRangeSet(RECS_Range r, RE_CharSet* s);

/**
 * @brief Union operation for two charsets
 * @param[in] p A set
 * @param[in] q A set
 * @returns The union of the sets @a p and @a q
 */
RE_CharSet* re_CSUnion(RE_CharSet* p, RE_CharSet* q);

/**
 * @brief Intersection operation for two charsets
 * @param[in] p A set
 * @param[in] q A set
 * @returns The intersection of the sets p and q
 */
RE_CharSet* re_CSIntersect(RE_CharSet* p, RE_CharSet* q);

/**
 * @brief Internal procedure for @ref re_CSSortInPlace
 * @param[in] r Range array
 * @return Useless
 */
int re_CS_qsort(RECS_Range* r, int n, int p);

/**
 * @brief Sorts the ranges of @a s in place
 * @param[in,out] s The set to be sorted in place
 * @return 1 if called on an empty set, 0 otherwise
 */
int re_CSSortInPlace(RE_CharSet* s);

/**
 * @brief Creates a sorted copy of @a s
 * @param[in] s The set to be sorted (not modified)
 * @return A sorted copy of @a s
 */
RE_CharSet* re_CSSort(RE_CharSet* s);

/**
 * @brief Iterator for charsets
 * @detailS Forward only
 */
typedef struct {
    /// @brief The current position
    LXAlphaType a;
    
    /// @brief The current range
    RECS_Range* i;
    
    /// @brief End of available ranges (one past the end of the array from the original charset)
    RECS_Range* stop;
} RE_CharSetIter;

#define RE_CSITER_GET(i) (i).a

#define RE_CSITER_CLEAR(i) LX_ALPHA_CLEAR((i).a)

/**
 * @brief Get the start iter
 */
RE_CharSetIter re_CSIStart(RE_CharSet* s);

/**
 * @brief Advance the iterator
 * @returns 1 if iterator is valid after the op, 0 otherwise
 */
int re_CSINext(RE_CharSetIter* i);

/**
 * @brief Is the iterator valid?
 * @returns 1 if the iterator is valid, 0 otherwise
 */
int re_CSIValid(RE_CharSetIter* i);

#ifdef __cplusplus
}//extern "C"
#endif

#endif
